#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    """
    @param A: an integer sorted array
    @param target: an integer to be inserted
    @return: An integer
    """
    def searchInsert(self, A, target):
        # write your code here
        if not A: return 0

        left = 0
        right = len(A) - 1

        while left != right - 1:
            # print('[%s, %s]' % (left, right))
            medium = (left + right) // 2
            med_v = A[medium]
            if target == med_v:
                return medium

            if target > med_v:
                left = medium
            else:
                right = medium

        # assert left == right
        if target <= A[left]:
            return left
        if target > A[right]:
            return right + 1
        return left + 1         # left < value <= right


def main():
    print("start main")
    s = Solution()
    assert s.searchInsert([1,3,5,6], 5) == 2
    assert s.searchInsert([1,3,5,6], 0) == 0
    assert s.searchInsert([1,3,5,6], 7) == 4


if __name__ == "__main__":
    main()
